package 力扣.数组;

import org.omg.CORBA.INTERNAL;

import java.util.HashMap;
import java.util.HashSet;

public class 等价多米诺骨牌对的数量1128 {
    public static void main(String[] args) {
        int[][] ints = {{1, 2}, {2, 1}, {3, 4}, {5, 6},{3,4},{3,4}};//4 = 1+ 1+2
//        int[][] ints = {{1, 2}, {2, 1}, {3, 4}, {5, 6},{3,4},{4,3},{4,3}};//7 = 1 + 1+2+3
//        int[][] ints = {{1, 2}, {2, 1}, {3, 4}, {5, 6},{3,4},{4,3},{4,3},{4,3}};//11 = 1 + 1+2+3+4
//        int[][] ints = {{1, 2}, {2, 1}, {3, 4}, {5, 6}, {6,7}};
//        int[][] ints = {{1, 2}};//0
//        int[][] ints = {{1, 2},{1,2},{1,1},{1,2},{2,2}};//3
        int i = numEquivDominoPairs2(ints);
        System.out.println(i);
    }

    /**
      原理：分析题目得：我们只需要记录一下‘二元组及其翻转二元组’出现的次数，然后再计算骨牌对的数量即可。
           （1）如何表示二元组？我们不妨直接让每一个二元对都变为指定的格式，即第一维必须不大于第二维。这样两个二元对「等价」当且仅当两个二元对完全相同
            即 int pe = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];

           （2）将二元组转为为一元以后就可以用数组或者hashmap记录其出现的次数了！

           （3）记录次数之后根据次数求出骨牌对的数量 这里有规律：出现次数p 股牌对数量q。但p = 2 时 q = 1 、p = 3 时 q = 1+2  p = 4 时 q = 1+2+3 。。。。
            即 q = 1 +.....+(p-1)。 利用‘延迟性’：我们使用数组或hashmap记录上一个一元整数的数量，然后更新总结果，最后更新一元整数的数量（即+1）。
     * @param dominoes
     * @return
     */
    public static int numEquivDominoPairs2(int[][] dominoes) {
        int re = 0;
        HashMap<Integer,Integer> reHm = new HashMap<>();
        for (int i = 0; i < dominoes.length; i++) {
            int[] domino = dominoes[i];
            int pe = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];//二元转一元
            if (reHm.containsKey(pe)){//若存在此元素
                int te2 = reHm.get(pe);//取出之前出现的次数
                re += te2;//加到最终结果上
                reHm.put(pe,++te2);//次数加一
            }else {
                reHm.put(pe, 1);
            }
        }
        return re;
    }
    public static int numEquivDominoPairs3(int[][] dominoes) {
        int[] num = new int[100];
        int ret = 0;
        for (int[] domino : dominoes) {
            int val = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];//二元转一元
            ret += num[val];//加上之前出现的次数
            num[val]++;//次数加一
        }
        return ret;
    }
}
